package dp;

import java.util.HashMap;
import java.util.Map;

public class P486 {
    public boolean PredictTheWinner(int[] nums) {
        Map<Integer, int[]> map = new HashMap<>();
        bt(nums, -1, 0, nums.length - 1, 0, new int[2], map);
        int[] item = map.get(0);
        int[] item2 = map.get(1);
        if (item[0] == 1 && item[1] == 0) {
            return true;
        } else if (item2[0] == 1 && item2[1] == 0) {
            return true;
        }
        return false;
    }

    //闭区间
    private boolean bt(int[] nums, int first, int start, int end, int order, int[] sum, Map<Integer, int[]> map) {
        if (start == 0 && end == nums.length - 1) {//闭区间
            //左
            first = nums[start];
            map.put(0, new int[]{0, 0});
            sum[0] += first;
            bt(nums, 0, 1, end, 1, sum, map);
            //右
            first = nums[end];
            map.put(1, new int[]{0, 0});
            sum[0] = 0;
            sum[1] += first;
            bt(nums, 1, 0, end - 1, 1, sum, map);
        } else if (start == end) {
            sum[order] += nums[start];
            int[] mapArray = map.get(first);
            if (sum[0] > sum[1]) {
                mapArray[0] = 1;
            } else {
                mapArray[1] = 1;
            }
            if (mapArray[0] + mapArray[1] == 2) {
                return false;
            }
        } else {
            //左
            int num = nums[start];
            sum[order] += num;
            if (!bt(nums, first, start + 1, end, (order + 1) % 2, sum, map)) {
                return false;
            }
            sum[order] -= num;
            //右
            num = nums[end];
            sum[order] += num;
            if (!bt(nums, first, start, end - 1, (order + 1) % 2, sum, map)) {
                return false;
            }
            sum[order] -= num;
        }
        return true;
    }


    /**
     * 递归计算总和
     */
    private int total(int[] nums, int start, int end, int turn) {
        if (start == end) {
            return nums[start] * turn;
        } else {
            int scoreStart = nums[start] * turn + total(nums, start + 1, end, -turn);
            int scoreEnd = nums[end] * turn + total(nums, start, end - 1, -turn);
            return Math.max(scoreStart, scoreEnd);
        }
    }

    public static void main(String[] args) {
        boolean flag = new P486().PredictTheWinner(new int[]{1, 5, 233, 7});
        System.out.println(flag);
    }

}
